package com.demo.datastructure.skipList;

/**
 * @description: 跳表的java实现
 * @author: ljr
 * @time: 2021/5/15 13:22
 */
public class SkipListDemo2 {

    private static final float SKIPLIST_P = 0.5f;

    private static final  int MAX_LEVEL = 16;

    private int levelCount = 1;

    private final Node head = new Node();

    public Node findValue(int value){
        Node p = head;
        for(int i = levelCount-1; i >= 0; i--){
            while (p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
        }
        if(p.forwards[0] != null && p.forwards[0].data == value){
            return p.forwards[0];
        }else{
            return null;
        }
    }


    public void insert(int value){
        int level = randomLevel();
        Node newNode = new Node();
        newNode.maxLevel = level;
        newNode.data = value;

        Node[] pervs = new Node[level];
        int i;
        for(i = 0; i < level; i++){
            pervs[i] = head;
        }


        Node p = head;
        for(i = level-1; i>=0; i--){
            while (p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
            pervs[i] = p;
        }

        for(i = 0; i < level; i++){
            newNode.forwards[i] =  pervs[i].forwards[i];
            pervs[i].forwards[i] = newNode;
        }

        if(levelCount < level) levelCount = level;
    }


    public void delete(int value){
        Node p = head;
        Node[] prev = new Node[levelCount];

        for(int i = levelCount-1; i >= 0; --i){
            while (p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
            prev[i] = p;
        }

        if(p.forwards[0] == null || p.forwards[0].data != value){
            return;
        }


        for(int i = 0; i < levelCount; i++){
            if(prev[i].forwards[i] == null || prev[i].forwards[i].data != value){
                continue;
            }
            prev[i].forwards[i] = prev[i].forwards[i].forwards[i];
        }

        while (levelCount>1&&head.forwards[levelCount]==null){
            levelCount--;
        }
    }

    private void printAll(){
        Node p = head;
        while (p.forwards[0] != null){
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }


    // 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
    // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
    // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
    //        50%的概率返回 1
    //        25%的概率返回 2
    //      12.5%的概率返回 3 ...
    private int randomLevel(){
        int level = 1;
        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
            level+=1;
        return level;
    }


    public class Node{
        private int data = -1;
        private final Node[] forwards = new Node[MAX_LEVEL];
        private int maxLevel = 0;

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{ data:");
            sb.append(data);
            sb.append("; levels: ");
            sb.append(maxLevel);
            sb.append(" }");
            return sb.toString();
        }
    }


    public static void main(String[] args) {
        int[] nums = new int[]{3,5,2,8,11,32,21};
        SkipListDemo2 skipListDemo2 = new SkipListDemo2();
        for(int i = 0; i < nums.length; i++){
            skipListDemo2.insert(nums[i]);
        }
        skipListDemo2.printAll();

        skipListDemo2.delete(2);
        skipListDemo2.printAll();
    }
}
